package com.sicheng.lc.lc笔试;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/31 19:42
 */
public class 途虎 {
    int[][] a;
    int up;
    Set<Integer>[] set;

    /**
     * nums分成 k组 每组有一个性质最大元素-最小元素：x = max - min
     * 求 所有组的x和的最小值,同组元素不重复
     * nums.length<=16 , k<=16
     */
    public int minimumIncompatibility(int[] nums, int k) {
        // write code here
        if (nums.length % k != 0) {
            return -1;
        }
        min = Integer.MAX_VALUE;
        a = new int[k][3];
        up = nums.length / k;
        for (int[] q : a) {
            q[1] = 20;
            q[2] = 0;
        }
        set = new HashSet[k];
        Arrays.setAll(set, kk -> new HashSet<>(64));
        dfs(0, nums, k);
        return min;
    }

    int min = Integer.MAX_VALUE;

    void dfs(int u, int[] nums, int k) {
        if (u == nums.length) {
            int sum = 0;
            for (int[] q : a) {
                sum += q[2] - q[1];
            }
            min = Math.min(sum, min);
            return;
        }

        for (int i = 0; i < k; i++) {
            if (a[i][0] >= up || set[i].contains(nums[u])) {
                continue;
            }

            a[i][0]++;
            set[i].add(nums[u]);
            int x = a[i][1];
            int y = a[i][2];
            a[i][1] = Math.min(a[i][1], nums[u]);
            a[i][2] = Math.max(a[i][2], nums[u]);
            dfs(u + 1, nums, k);
            a[i][0]--;
            set[i].remove(nums[u]);
            a[i][1] = x;
            a[i][2] = y;
        }
    }

    public static void main(String[] args) {

    }
}
